The use of remote computing services, such as remote program execution services and remote data storage services has greatly increased in recent years. Customers may purchase these services from a computing resource service provider and customer applications may be distributed over multiple virtual machine instances running on one or more computing systems. In many cases, these virtual machine instances run under a virtualization layer that exposes a logical volume using a block-level storage device on a data storage server for storage. However, determining how a block-level storage volume should be partitioned for optimal performance can be challenging, particularly when different partitioning schemes perform differently depending on volume usage and the state of the computer system.